package lib;

import java.util.concurrent.*;

public class Sort {
    private int[] intArray = null;

    public Sort(int[] array) {
        if (array == null) throw new NullPointerException();
        intArray = array;
    }

    //插入排序
    public static void insertionSort(int arr[]) {
        insertionSort(arr, 0, arr.length);
    }

    //对数组的一部分进行插入排序
    //函数处理数组的[left,right-1]部分
    private static void insertionSort(int[] arr, int left, int right) {
        if (right <= left) throw new IllegalArgumentException("Right index less than or equals to left index.");
        int i, j;
        for (i = left + 1; i <= right - 1; i++) {
            int key = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > key) arr[j + 1] = arr[j];
                else break;
            }
            arr[j + 1] = key;
        }
    }

    //快速排序
    //函数处理数组的[left,right-1]部分
    private static void qsort(int[] arr, int left, int right) {
        if (right <= left) throw new IllegalArgumentException("Right index less than or equals to left index.");
        if (right - left <= 20) {
            insertionSort(arr);
            return;
        }
        int low = left;
        int high = right - 1;
        int medium = (low + high) / 2;

        // Medium-of-Three方法选择枢轴
        //目标: arr[medium] <= arr[high]
        if (arr[medium] > arr[high]) {
            swap(arr, medium, high);
        }
        //目标: arr[low] <= arr[high]
        if (arr[low] > arr[high]) {
            swap(arr, low, high);
        }
        //目标: arr[low] >= arr[medium]
        if (arr[medium] > arr[low]) {
            swap(arr, medium, low);
        }

        //分割数组
        int pivot = arr[low];
//        while (low != high) {
//            while (low != high) {
//                if (arr[high] >= pivot) high--;
//                else {
//                    arr[low] = arr[high];
//                    break;
//                }
//            }
//            while (low != high) {
//                if (arr[low] <= pivot) low++;
//                else {
//                    arr[high] = arr[low];
//                    break;
//                }
//            }
//        }
        while (true) {
            while (low != high && arr[high] >= pivot) high--;
            if (low != high) arr[low] = arr[high];
            else break;
            while (low != high && arr[low] <= pivot) low++;
            if (low != high) arr[high] = arr[low];
            else break;
        }
        int pivotIndex = low;
        arr[pivotIndex] = pivot;

        //递归
        qsort(arr, left, pivotIndex);
        qsort(arr, pivotIndex + 1, right);
    }

    //快速排序
    //调用qsort(int[] arr, int left, int right)
    public static void qsort(int[] arr) {
        qsort(arr, 0, arr.length);
    }

    //并行快速排序
    //基于ForkJoin框架
    public void parallelQSort() {
        ForkJoinPool pool = new ForkJoinPool();
        ParallelQSortTask masterTask = new ParallelQSortTask(0, intArray.length);
        pool.invoke(masterTask);
    }

    //交换数组中两个元素的位置
    private static void swap(int[] arr, int indexA, int indexB) {
        int tmp = arr[indexA];
        arr[indexA] = arr[indexB];
        arr[indexB] = tmp;
    }

    //用于并行快速排序的内部类
    class ParallelQSortTask extends RecursiveAction {
        private final int left;
        private final int right;

        public ParallelQSortTask(int left, int right) {
            if (right <= left) throw new IllegalArgumentException("Right index less than or equals to left index.");
            this.left = left;
            this.right = right;
        }

        public void compute() {
            //问题规模小，串行解决
            if (right - left <= 20) {
                insertionSort(intArray, left, right);
                return;
            }
            int low = left;
            int high = right - 1;
            int medium = (low + high) / 2;

            // Medium-of-Three方法选择枢轴
            //目标: arr[medium] <= arr[high]
            if (intArray[medium] > intArray[high]) {
                swap(intArray, medium, high);
            }
            //目标: arr[low] <= arr[high]
            if (intArray[low] > intArray[high]) {
                swap(intArray, low, high);
            }
            //目标: arr[low] >= arr[medium]
            if (intArray[medium] > intArray[low]) {
                swap(intArray, medium, low);
            }

            //分割数组
            int pivot = intArray[low];
            while (true) {
                while (low != high && intArray[high] >= pivot) high--;
                if (low != high) intArray[low] = intArray[high];
                else break;
                while (low != high && intArray[low] <= pivot) low++;
                if (low != high) intArray[high] = intArray[low];
                else break;
            }
            int pivotIndex = low;
            intArray[pivotIndex] = pivot;

            ParallelQSortTask leftTask = new ParallelQSortTask(left, pivotIndex);
            ParallelQSortTask rightTask = new ParallelQSortTask(pivotIndex + 1, right);
            leftTask.invoke();
            rightTask.invoke();
        }
    }
}
